package 余数的最大值;

import java.util.*;

public class Main {
    static int N = 34, n, m;
    static int[] w = new int[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for (int i = 0; i < n; i++) {
            w[i] = in.nextInt();
        }
        List<Integer> A = new ArrayList<>();
        List<Integer> B = new ArrayList<>();
        dfs(0, n / 2, 0, A);
        dfs(n / 2, n, 0, B);
        Collections.sort(A);
        Collections.sort(B);
        int res = (A.get(A.size() - 1) + B.get(B.size() - 1)) % m;
        for (int i = 0, j = B.size() - 1; i < A.size(); i++) {
            while (j >= 0 && A.get(i) + B.get(j) >= m) {
                j--;
            }
            if (j >= 0) {
                res = Math.max(res, (A.get(i) + B.get(j)) % m);
            }
        }
        System.out.println(res);
    }

    private static void dfs(int l, int r, int s, List<Integer> arr) {
        if (l == r) {
            arr.add(s);
            return;
        }
        dfs(l + 1, r, s, arr);
        dfs(l + 1, r, (s + w[l]) % m, arr);
    }
}
